package com.linran.structure_algorithm.算法.lesson2_排序;

import java.time.Duration;
import java.time.LocalDateTime;

/**
 * 基数排序
 * 空间换时间一种排序
 */
public class RadixSort {

    public static void main(String[] args) {
        int base = 8000000;
        int[] arr = new int[base];
        for (int i = 0; i < base - 1; i++) {
            arr[i] = (int) (Math.random() * base);
        }
        LocalDateTime start = LocalDateTime.now();
        //线性增长，合并次数为arr.length - 1 次
        radixSort(arr);// new int[arr.length]临时数组，多一份空间
        LocalDateTime end = LocalDateTime.now();
        System.out.println("排序后的数组");
        System.out.printf("耗时:%d毫秒%n", Duration.between(start, end).toMillis());
    }

    public static void radixSort(int[] arr) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        for (int m = 0; m < maxLength; m++) {
            int[][] bucket = new int[10][arr.length];
            int[] bucketPos = new int[10];
            for (int i = 0; i < arr.length; i++) {
                int bucketIndex = arr[i] / (int) Math.pow(10, m) % 10;
                bucket[bucketIndex][bucketPos[bucketIndex]] = arr[i];
                bucketPos[bucketIndex]++;
            }
            int tempIndex = 0; //还原回去数组下标
            for (int i = 0; i < 10; i++) {
                if (bucketPos[i] != 0) {
                    for (int j = 0; j < bucketPos[i]; j++) {
                        arr[tempIndex] = bucket[i][j];
                        tempIndex++;
                    }
                    bucketPos[i] = 0;
                }
            }
//            System.out.printf("第%d轮排序%n", m + 1);
        }
//        System.out.println(Arrays.toString(arr));
    }

//    public static void radixSort(int[] arr) {
//        int[][] bucket = new int[10][arr.length];
//        int[] bucketPos = new int[10];
//        //第一轮
//        for (int i = 0; i < arr.length; i++) {
//            int bucketIndex = arr[i] % 10;
//            bucket[bucketIndex][bucketPos[bucketIndex]] = arr[i];
//            bucketPos[bucketIndex]++;
//        }
//        int tempIndex = 0; //还原回去数组下标
//        for (int i = 0; i < 10; i++) {
//            if (bucketPos[i] != 0) {
//                for (int j = 0; j < bucketPos[i]; j++) {
//                    arr[tempIndex] = bucket[i][j];
//                    tempIndex++;
//                }
//                bucketPos[i] = 0;
//            }
//        }
//        tempIndex = 0;
//        System.out.println(Arrays.toString(arr));
//
//        //第二轮
//        for (int i = 0; i < arr.length; i++) {
//            int bucketIndex = arr[i] / 10 % 10;
//            bucket[bucketIndex][bucketPos[bucketIndex]] = arr[i];
//            bucketPos[bucketIndex]++;
//        }
//        for (int i = 0; i < 10; i++) {
//            if (bucketPos[i] != 0) {
//                for (int j = 0; j < bucketPos[i]; j++) {
//                    arr[tempIndex] = bucket[i][j];
//                    tempIndex++;
//                }
//                bucketPos[i] = 0;
//            }
//        }
//        tempIndex = 0;
//        System.out.println(Arrays.toString(arr));
//    }
}